/* 用层次遍历求解二叉树的高度 */

#include <iostream>
#include "BiTreefun.h"
using namespace std;
#define maxsize 50

// 求二叉树的高度
int depth(BTNode *boot)
{
  // 如果二叉树为空
  if (boot == NULL)
    return 0; // 高度为0
  
  // 创建队列
  int front = 0, rear = 0;
  BTNode *q[maxsize];
  
  // 记录一层中最后一个结点的序号，当前所在的层次
  int last = 1, level = 0;
  
  // 根结点进队
  q[++rear] = boot;
  
  BTNode *p;
  
  // 如果队列不为空 -- 层次遍历
  while (front < rear)
  {
    // 结点出队
    p = q[++front];
    
    // 左孩子结点进队
    if (p->lchild)
      q[++rear] = p->lchild;
    
    // 右孩子结点进队
    if (p->rchild)
      q[++rear] = p->rchild;
    
    // 如果到达一层中的最后一个结点
    if (front == last)
    {
      level++; // 访问下一层
      last = rear; // 更新一层中最后一层的序号
    }
  }
  
  // 返回层数 -- 高度
  return level;
}

int main()
{
  // 创建二叉树
  BTNode *T = create_bitree();
  cout << "二叉树的高度为:" << depth(T) << endl;
}